package com.faiz.algorithm;


public class Codec {
    // 使用前序遍历的方法来进行序列化和反序列化
    private static final String NULL = "null";

    private static final String SEPARATOR = ",";

    public static class Preorder {
        private int index = 0;

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            serialize(root, sb);
            return sb.deleteCharAt(sb.length() - 1).toString();
        }

        private void serialize(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append(NULL).append(SEPARATOR);
                return;
            }

            sb.append(root.val).append(SEPARATOR);

            serialize(root.left, sb);
            serialize(root.right, sb);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] sequence = data.split(SEPARATOR);
            return deserialize(sequence);
        }

        private TreeNode deserialize(String[] sequence) {
            if (index >= sequence.length) return null;

            TreeNode root;
            if (NULL.equals(sequence[index])) {
                root = null;
                return root;
            }
            else root = new TreeNode(Integer.parseInt(sequence[index]));
            index++;
            root.left = deserialize(sequence);
            index++;
            root.right = deserialize(sequence);

            return root;
        }

    }

    public static class Postorder {
        private int index = 0;

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            serialize(root, sb);
            return sb.deleteCharAt(sb.length() - 1).toString();
        }

        private void serialize(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append(NULL).append(SEPARATOR);
                return;
            }
            serialize(root.left, sb);
            serialize(root.right, sb);
            sb.append(root.val).append(SEPARATOR);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] sequence = data.split(SEPARATOR);
            index = sequence.length - 1;
            return deserialize(sequence);
        }

        private TreeNode deserialize(String[] sequence) {
            if (index < 0) return null;

            TreeNode root;
            if (NULL.equals(sequence[index])) {
                root = null;
                return root;
            }
            else root = new TreeNode(Integer.parseInt(sequence[index]));
            index--;
            root.right = deserialize(sequence);
            index--;
            root.left = deserialize(sequence);
            return root;
        }
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

        Codec.Preorder codec = new Codec.Preorder();
        String serialize = codec.serialize(root);
        System.out.println(serialize);

        TreeNode treeRoot = codec.deserialize(serialize);
        System.out.println("ok");
    }
}
